package ClassicalSortingAlgorithm;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: ClassicalSortingAlgorithm
 * @Author: song
 * @CreateTime: 2022-09-17  16:10
 * @Description: 稳定性：不稳定
 * 时间复杂度 ：最佳：O(n2) ，最差：O(n2)， 平均：O(n2)
 * 空间复杂度 ：O(1)
 * 排序方式 ：In-place
 * @Version: 1.0
 */

public class selectSort {
    public static void main(String[] args) {
        int[] nums = {5,1,3,78,49,32,14,2,96,55,11};
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        selectSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
    public static int[] selectSort(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i; // 记录每一轮循环最小的那个数在数组中的位置；
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[minIndex] > nums[j]){
                    minIndex = j;
                }
            }
            // 如果在当前本轮循环中，minIndex的值发生了变换，就将当前这轮num[i]和num[minIndex]交换位置；
            if (minIndex != i){
                int temp = nums[minIndex];
                nums[minIndex] = nums[i];
                nums[i] = temp;
            }
        }

        return nums;
    }
}
